package 算法.排序算法;

public class 快速排序 {
    public static void main(String[] args) {
        /*
        快速排序：
            第一轮：以0号索引的数字为基准数，确定基准数在数组中正确的位置。
            比基准数小的全部在左边，比基准数大的全部在右边。
            后面以此类推。
      */

        int[] arr = {6,1, 2, 7, 9, 3, 4, 5,10, 8};
        quickSort(arr,0,arr.length-1);

        //循环数组
        for (int j : arr) {
            System.out.print(j+" ");
        }
    }

    public static void quickSort(int[] arr,int i,int j){
        //定义两个变量记录要查找的范围
        int start=i;      //start:找比基准数大的的元素
        int end=j;        //找基准数小的元素的元素

        //递归出口
        if (start>end){
            return;
        }

        //记录基准数
        int baseNumber=arr[i];

        //1.利用循环找到要交换元素(找到start,end)
            //start:从前往后找,找比基准数大的数字
        while (start!=end) {

            //end:从前往后找,找到基准数小的元素
            while(true){
                if (arr[end]<baseNumber||end<=start){break;}
                end--;
            }
            while (true){
                if (arr[start]>baseNumber||end<=start) {
                    break;
                }
                start++;
            }
            //把end和start的元素进行互换
            int temp=arr[start];
            arr[start]=arr[end];
            arr[end]=temp;
            }
        //当start和end指向了同一个元素的时候上面的循环就会结束
        //此时就找到了基准数对应的位置
        //基准数归位--->用此时的基准数跟归为的位置对应的数字进行交换
        int tem=arr[i];
        arr[i]=arr[start];
        arr[start]=tem;

        //确认6左边的范围重复上述操作
        quickSort(arr,0,start-1);

        //确认6左边的范围重复上述操作
        quickSort(arr,end+1,j);
    }
}
